With the increased proliferation of data processing devices and with increased availability of computer networks for data exchange an increasing number of services can be obtained using for example home computer equipment or similar.
Generally, the provision of a service via a computer network requires a transmission device or server for transmitting data pertaining to the service and requires a receiving device or client for receiving the data from the server. A user operating the receiving device may then appropriately take notice of the received data, e.g. view the received data on a display, or listen to audio data. Interactive services enable users to control the service provision via entering information at the client for transmission to the server, thus enabling the server to appropriately configure the service provision.
Providing a service over a computer network may require the exchange of substantial amounts of data, for example image or audio data, and as the network bandwidth available for the streaming is generally limited, data compression or coding is applied. These techniques reduce the amount of data to be transmitted via the network, preferably without substantially degrading the quality of the data obtained at the receiver. Many data compression techniques for image data including video and audio data are available today.
One group of services available over computer networks includes the transmission of data streams from a transmitting device to a receiving device. The data stream may incorporate a sequence of images, such as video sequence, or may incorporate audio data or both. For example, a user at a client computer device may obtain a steaming service by appropriately selecting an offered data stream, e.g. by clicking on a corresponding icon on a browser screen. The user can view a browser page on a client display including for example a selection of text elements accompanied by a tag offering a corresponding video sequence. The user can then select a desired tag and a selection instruction will be transmitted to a server, requesting the server to initiate transmission of a corresponding video data stream to the client device. The client device in turn will then display the video sequence.
As a data stream usually contains a large amount of data to be transmitted on the relatively strict time constraints, e.g. for maintaining real time requirements, efficient data compression techniques or codes are required.
Streaming applications generally involve the use of predictive coding. A data stream is usually formed by a sequential transmission of a number of data elements, each of the data elements representing a portion of the information to be streamed to the receiving device. Predictive coding includes any data compression or coding technique, where at least some of the data elements refer to or require information transmitted in other data elements. A data element requiring information from another data element can therefore be decompressed at the receiving device only to full extent, if the required further data element or data elements are available at the receiving device. For example, predictive coding may include a statistical estimation procedure where future random variables of the data stream are estimated or predicted from past and present observable random variables.
Streaming applications between computers may be hampered by a lack of service support. Generally it is difficult to reserve a bandwidth, e.g. on a computer network, for the streaming application and for this reason a transmitting device may be unable to transmit the complete streaming information to the receiving device in a timely manner. Moreover, in a streaming application data elements usually contain a time stamp indicating a temporal position within the stream. Consequently, for maintaining real time conditions, a data element must be available at the receiving device at a certain point in time, to allow a timely presentation of the data elements. If not all data elements of the streaming application can be transmitted in a timely manner to the receiving device, a video, audio or other data stream may be interrupted or fully terminated.
In an environment with a limited available bandwidth it is thus required to carefully schedule the individual data elements for transmission to the receiving device, in order to maintain the highest possible quality of the data stream. Further, it is required to appropriately scale down a required bandwidth for the data stream transmission while accepting a more or less severe reduction of the quality of the stream but avoiding dropouts or termination of services.
As in a limited bandwidth environment it may not be possible to transmit all data elements of the data stream, a careful selection of the most important ones of the data elements for the data stream should be performed, in order to avoid the dropping of highly important data elements when the available bandwidth is exhausted. Ideally, only the least important data packets should be dropped upon reaching a bandwidth limitation.
A simple scheduling algorithm is the so-called earliest deadline first (EDF) algorithm proposed by C. L. Liu and J. W. Layland, “Scheduling algorithms for multiprogramming in a hard-real-time environment,”, Journal of the ACM (JACM), vol. 20, no. 1, pp. 46-61, January 1973. In this approach data elements are transmitted in their presentation order, in order to make sure that the data elements arrive in a timely manner at the receiving device. In another approach described in W. chi Feng, M. Liu, B. Krishnaswami, and A. Prabhudev, “A priority-based technique for the best-effort delivery of stored video,” in SPIE/IS&T Multimedia Computing and Networking 1999, January 1999, priority values are assigned to the data elements, indicating the relative importance of frames. A priority-based transmission scheme minimizing a weighted loss of data elements has been described in reference (4): R. L. Givan, E. K. P. Chong, and H. S. Chang, “Scheduling multiclass packet streams to minimize weighted loss,” in Queueing Systems, vol. 41, no. 3, January 2001, pp. 241-270. In a priority-based scheduling the highest priority data elements are transmitted and only after transmission of the highest priority packets a transmission turns to some of the next lower priority data elements. Accordingly, a transmission order can be different from a playout order at the receiving device. If in this priority-based scheme an available bandwidth is not sufficient, the data elements with lower priorities are dropped from the transmission queue, as the bandwidth limitation is reached. In a practical case the data elements with lower priorities will be dropped due to reaching the above-mentioned playout time limit, after which a time representation of the data element is not any longer possible. This algorithm assures that always data elements of higher priorities are transmitted first and thus available at the receiving device and, if the bandwidth is insufficient for transmitting all data elements, that lower priority data elements are skipped. This will lead to a more or less severe degradation of the overall quality of the stream. However, this algorithm has drawbacks during start-up conditions, as it will take relatively long periods of time until the data packets with lower priorities are transmitted.